//
// Description: 739. 每日温度
// Created by Loading on 2022/8/1.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> dailyTemperatures(vector<int> &temperatures) {
    int n = temperatures.size();
    // 单调栈，存储还未确认的下标，其对应温度依次递减
    stack<int> stk;
    vector<int> res(n);
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
            // 找到第一个比栈顶元素温度高的下标
            int index = stk.top();
            stk.pop();
            res[index] = i - index;
        }
        stk.emplace(i);
    }

    return res;
}

int main() {
    vector<int> temperatures{30, 60, 90};

    auto res = dailyTemperatures(temperatures);

    for (auto x : res) {
        cout << x << ' ';
    }

    return 0;
}